#ifndef SORTEDLIST_H
#define SORTEDLIST_H

#include "list.h"
#include "comparator.h"

namespace Library
{

template<class O> class SortedListIterator;

/**
 * A template that implements a sort linked list.  Duplicate objects are
 * allowed.
 */
template<class O> 
class SortedList : public List<O>
{
	public:
						SortedList(Comparator<O> * comparator);
		virtual			~SortedList();

		// Collection overrides
		virtual bool8	add(O object);

		// List overrides
		virtual bool8	addIndex(uint32 index, O object);
		virtual O 		setIndex(uint32 index, O object);

		// SortedList originals
		virtual bool8	addLast(O object);

		// Iterators
		virtual ListIterator<O> * listIterator();
		virtual ListIterator<O> * listIterator(uint32 index);

		virtual SortedListIterator<O> * sortedListIterator();
		virtual SortedListIterator<O> * sortedListIterator(uint32 index);

	protected:
		Comparator<O> *	m_comparator;

	// prohibited
	private:
		SortedList();
		SortedList(Collection<O> &);
		SortedList & operator=(Collection<O> &);
};


template<class O>
class SortedListIterator : public ListIterator<O>
{
	public:
						SortedListIterator(SortedList<O>* list, uint32 index=0);
		virtual			~SortedListIterator();

		// Iterator overrides (none)

		// ListIterator overrides
		virtual bool8	add(O object);
		virtual O		set(O object);

		// Sorted originals (none)

	private:
		// ListIterator prohibited

	// prohibited
	private:
		SortedListIterator();
		SortedListIterator(Iterator<O> &);
		SortedListIterator & operator=(Iterator<O> &);
};


//============================================================================
// SortedList
//============================================================================

//----------------------------------------------------------------------------
// Public
//

/**
 * A constructor that take a pointer to a Comparator.  The comparator will
 * be deleted by the SortedList when it's deleted.
 */
template<class O>
SortedList<O>::SortedList(Comparator<O> * comparator)
{
	m_comparator = comparator;
}

/**
 * The destructor.  SortedList is responsible for deleting the Comparator.
 */
template<class O>
SortedList<O>::~SortedList()
{
	delete m_comparator;
}

/**
 * Adds an object to the SortedList via insertion sort.  Since duplicate
 * objects are allowed, this method inserts objects in front of their
 * identical self (as defined by the Comparator).
 *
 * Example:
 *		If a sorted list already contains (0 1 2 4 5) the addition of (4)
 *		will be inserted as (0 1 2 [4] 4 5).  The [4] indicates the location.
 */
template<class O> bool8
SortedList<O>::add(O object)
{
	ListEntry<O> * entry = new ListEntry<O>(object);
	ListEntry<O> * prev;
	ListEntry<O> * next;

	if (entry)
	{
		if (!m_head)
			m_head = m_tail = entry;
		else
		{
			prev = 0;
			next = m_head;

			while (next)
			{
				if (m_comparator->compare(next->m_object, object) >= 0)
					break;

				prev = next;
				next = next->m_next;
			}

			if (prev)
			{
				prev->m_next = entry;
				entry->m_prev = prev;
			}
			else
				m_head = entry;

			if (next)
			{
				next->m_prev = entry;
				entry->m_next = next;
			}
			else
				m_tail = entry;
		}

		m_size++;
		m_age++;
	}

	return (bool8)(entry != 0);
}

/**
 * To preserve the integrity of the sorted list, index insertions are not
 * allowed.  As such, any call to this method will return false.
 */
template<class O> bool8
SortedList<O>::addIndex(uint32 index, O object)
{
	return false;
}

/**
 * Adds an object to the SortedList via insertion sort.  Since duplicate
 * objects are allowed, this method inserts objects after of their
 * identical self (as defined by the Comparator).
 *
 * Example:
 *		If a sorted list already contains (0 1 2 4 5) the addition of (4)
 *		will be inserted as (0 1 2 4 [4] 5).  The [4] indicates the location.
 */
template<class O> bool8
SortedList<O>::addLast(O object)
{
	ListEntry<O> * entry = new ListEntry<O>(object);
	ListEntry<O> * prev;
	ListEntry<O> * next;

	if (entry)
	{
		if (!m_head)
			m_head = m_tail = entry;
		else
		{
			prev = 0;
			next = m_head;

			while (next)
			{
				if (m_comparator->compare(next->m_object, object) > 0)
					break;

				prev = next;
				next = next->m_next;
			}

			if (prev)
			{
				prev->m_next = entry;
				entry->m_prev = prev;
			}
			else
				m_head = entry;

			if (next)
			{
				next->m_prev = entry;
				entry->m_next = next;
			}
			else
				m_tail = entry;
		}

		m_size++;
		m_age++;
	}

	return (bool8)(entry != 0);
}

/**
 * Returns a pointer to a ListIterator pointing to the beginning of the
 * List.  The calling class is responsible for deleting the list iterator
 * when finished.
 */
template<class O> ListIterator<O> *
SortedList<O>::listIterator()
{
	return sortedListIterator();
}

/**
 * Returns a pointer to a ListIterator pointing to index @p index in the
 * List.  The calling class is responsible for deleting the list iterator
 * when finished.
 */
template<class O> ListIterator<O> *
SortedList<O>::listIterator(uint32 index)
{
	return sortedListIterator(index);
}

/**
 * To preserve the integrity of the sorted list, set operations are not
 * allowed.  As such, any call to this method will return 0.
 */
template<class O> O
SortedList<O>::setIndex(uint32 index, O object)
{
	return 0;
}

/**
 * Returns a pointer to a SortedListIterator pointing to the beginning of the
 * List.  The calling class is responsible for deleting the list iterator
 * when finished.
 */
template<class O> SortedListIterator<O> *
SortedList<O>::sortedListIterator()
{
	return new SortedListIterator<O>(this, 0);
}

/**
 * Returns a pointer to a SortedListIterator pointing to index @p index in the
 * List.  The calling class is responsible for deleting the list iterator
 * when finished.
 */
template<class O> SortedListIterator<O> *
SortedList<O>::sortedListIterator(uint32 index)
{
	return new SortedListIterator<O>(this, index);
}


//============================================================================
// SortedListIterator
//============================================================================

//----------------------------------------------------------------------------
// Public
//

/**
 * A construct which creates a SortedListIterator for SortedList @p list.
 * The start position of the iterator is optionally specified by @p index.
 */
template<class O>
SortedListIterator<O>::SortedListIterator(SortedList<O> * list, uint32 index)
	: ListIterator<O>(list, index)
{
}

template<class O>
SortedListIterator<O>::~SortedListIterator()
{
}

/**
 * Adds an object to the list.  The object is sorted into the list and has no
 * bearing the location of the iterator.
 */
template<class O> bool8
SortedListIterator<O>::add(O object)
{
	return m_list->add(object);
}

/**
 * To preserve the integrity of the sorted list, set operations are not
 * allowed.  As such, any call to this method will return 0.
 */
template<class O> O
SortedListIterator<O>::set(O object)
{
	return 0;
}

};

#endif
